#include <string.h>

int Min(int a, int b)
{
    return a < b ? a : b;
}

//获取以特殊符号间隔开后的字符串
//如：传入「abbc」，输出「#a#b#b#c#」
char* GetManacherStr(const char* str)
{
    int i = 0, j = 0;
    char *manacherStr = (char *)malloc(sizeof(char) * (strlen(str) * 2 + 2));
    while(str[i] != '\0')
    {
        manacherStr[j++] = '#';//加入任意字符都不影响Manacher
        manacherStr[j++] = str[i++];
    }
    manacherStr[j++] = '#';//结尾也要补一个
    manacherStr[j] = '\0';//别忘了结尾的'\0'
    return manacherStr;
}

//Manacher算法，用于获取最大回文子串长度
int GetMaxCpsLenght(const char *str)
{
    int center = -1; //当前最右回文中心
    int right = -1; //当前最右回文右边界
    char *m_str = GetManacherStr(str);
    int len = strlen(m_str);
    //记录该位置字符为中心的最大回文半径（包括自身）
    int *cpsR_Arr = (int *)malloc(sizeof(int) * len);
    int resMax = -10; //记录整体最大回文长度
    for (int i = 0; i < len; ++i)
    {
        cpsR_Arr[i] = right > i ? Min(cpsR_Arr[center * 2 - i], right - i) : 1;
        while(i + cpsR_Arr[i] < len && i - cpsR_Arr[i] >= 0)
        {
            if(m_str[i + cpsR_Arr[i]] == m_str[i - cpsR_Arr[i]])
                ++cpsR_Arr[i];
            else break;
        }
        if(i + cpsR_Arr[i] > right)//当前回文右边界 > 最右回文边界
        {
            right = i + cpsR_Arr[i];//更新最右回文右边界
            center = i;//更新中心
        }
        if(cpsR_Arr[i] > resMax)//更新最大回文长度
            resMax = cpsR_Arr[i];
    }
    //因为m_str扩大了一倍，所以回文长度= m_str回文半径 - 1（结尾字符）
    return resMax - 1;
}